package 搜索.BFS;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class 滑动谜题_773 {

    public static void main(String[] args) {
        System.out.println(new 滑动谜题_773().slidingPuzzle(new int[][]{{1, 2, 3}, {4, 0, 5}}));
    }

    public int slidingPuzzle(int[][] board) {
        int m = 2;
        int n = 3;
        String start = "";
        StringBuffer sb = new StringBuffer();
        String target = "123450";
        //将2*3的数组转化成一个字符串
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(board[i][j]);
                start = sb.toString();
            }
        }

        //记录在一维字符串中 某个元素在 原来二维数组 中的 相邻元素 的索引。
        int[][] neighbor = new int[][]{
                {1, 3},
                {0, 4, 2},
                {1, 5},
                {0, 4},
                {3, 1, 5},
                {4, 2}
        };

        /*开始BFS*/
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();


        q.offer(start);
        visited.add(start);
        int step = 0;//因为start就是初始值，没有动过，所以步数不需要从1开始

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();

                if (cur.equals(target)) {
                    return step;
                }

                //idx用来保存‘0’的索引。因为我们只可以移动‘0’
                int idx = 0;
                //这个循环就是从字符串中找到‘0’的索引
                for (; cur.charAt(idx) != '0'; idx++) {
                }

                //交换0和相邻元素的位置
//                neighbor[idx]：和0在二维数组中相邻元素的索引
                for (int adj : neighbor[idx]) {
                    String new_board = cur;
                    new_board = exchangeString(new_board, idx, adj);

                    if (!visited.contains(new_board)) {
                        q.offer(new_board);
                        visited.add(new_board);
                    }
                }
            }
            step++;
        }

        return -1;
    }


    /**
     * 交换字符
     *
     * @param string
     * @param src
     * @param dis
     * @return
     */
    public String exchangeString(String string, int src, int dis) {
        char[] chars = string.toCharArray();
        char temp = chars[dis];
        chars[dis] = chars[src];
        chars[src] = temp;
        return new String(chars);
    }
}
